#pragma once
#include<iostream>
using namespace std;

namespace xlf
{
	// 节点的定义
	template<class T>// 参数模板，只能供当前类或当前函数使用
	struct ListNode // struct 访问限定符为公有
	{
		ListNode<T>* _prev;// 指向前一个节点的指针
		ListNode<T>* _next;// 指向后一个节点的指针

		T _data;// 节点的数据

		//带参构造
		ListNode(const T& data)
			:_prev(nullptr)
			,_next(nullptr)
			,_data(data)
		{}
	};

	//// 堆迭代器进行封装
	//template<class T>
	//struct ListIterator
	//{
	//	typedef ListNode<T> Node;
	//	typedef ListIterator<T> Self;
	//	Node* _node;

	//public:
	//	ListIterator(Node* node)
	//		:_node(node)
	//	{}

	//	Self& operator++()
	//	{
	//		_node = _node->_next;
	//		return *this;
	//	}

	//	// & : *this出了作用域不销毁
	//	Self& operator--()
	//	{
	//		_node = _node->_prev;
	//		return *this;
	//	}
	//	// 传值返回， temp出了作用域就销毁
	//	Self operator++(int)//后置， 返回的是++之前的值
	//	{
	//		Node* temp(*this);// 先保留之前的值
	//		_node = _node->_next;
	//		return temp;
	//	}

	//	Self operator--(int)
	//	{
	//		Node* tmp(*this);
	//		_node = _node->_prev;
	//		return tmp;
	//	}

	//	bool operator!=(const Self& it) { return _node != it._node; }
	//	bool operator==(const Self& it) { return _node == it._node; }

	//	T& operator*() { return _node->_data; }
	//	const T* operator->() { return &_node->_data; }
	//};

	//// const_iterator
	//	//链表迭代器
	//template<class T>
	//struct ListConstIterator
	//{
	//	typedef ListNode<T> Node;//给节点取别名
	//	typedef ListConstIterator<T> Self;//給迭代器取别名
	//	Node* _node;//节点

	//public:
	//	//构造函数
	//	ListConstIterator(Node* node)
	//		:_node(node)
	//	{}

	//	//对自定义进行运算符的重载，可控制迭代器的行为

	//	Self& operator++()
	//	{
	//		_node = _node->_next;
	//		return *this;
	//	}

	//	Self& operator--()
	//	{
	//		_node = _node->_prev;
	//		return *this;
	//	}

	//	Self operator++(int)
	//	{
	//		Node* temp(*this);
	//		_node = _node->_next;
	//		return temp;
	//	}

	//	Self operator--(int)
	//	{
	//		Node* temp(*this);
	//		_node = _node->_prev;
	//		return temp;
	//	}

	//	bool operator!=(const Self& it)
	//	{
	//		return _node != it._node;
	//	}

	//	bool operator==(const Self& it)
	//	{
	//		return _node == it._node;
	//	}

	//	const T& operator*()
	//	{
	//		return _node->_data;
	//	}

	//	const T* operator->()
	//	{
	//		return &_node->_data;
	//	}
	//};

	//迭代器的第二种写法：
	//template 定义的模板参数，只能供当前类或当前函数使用
	//链表迭代器
	template<class T, class Ref, class Ptr>
	struct ListIterator
	{
		typedef ListNode<T> Node;//给节点取别名
		typedef ListIterator<T, Ref, Ptr> Self;//給迭代器取别名

		Node* _node;//节点

	public:
		//构造函数
		ListIterator(Node* node)
			:_node(node)
		{}

		//对自定义进行运算符的重载，可控制迭代器的行为

		Self& operator++()
		{
			_node = _node->_next;
			return *this;
		}

		Self& operator--()
		{
			_node = _node->_prev;
			return *this;
		}

		Self operator++(int)
		{
			Node* temp(*this);
			_node = _node->_next;
			return temp;
		}

		Self operator--(int)
		{
			Node* temp(*this);
			_node = _node->_prev;
			return temp;
		}

		bool operator!=(const Self& it)
		{
			return _node != it._node;
		}

		bool operator==(const Self& it)
		{
			return _node == it._node;
		}

		Ref operator*()
		{
			return _node->_data;
		}
	
		Ptr operator->()
		{
			return &_node->_data;
		}
	};


	template<class T>
	class List
	{
		typedef ListNode<T> Node;
	public:
		List()
		{
			_head = new Node(T());
			_head->_prev = _head;
			_head->_next = _head;
		}

		void push_back(const T& x)
		{
			Node* newnode = new Node(x);
			Node* tail = _head->_prev;

			// prev newnode next
			tail->_next = newnode;
			newnode->_prev = tail;
			newnode->_next = _head;
			_head->_prev = newnode;
		}

		typedef ListIterator<T> iterator;

		iterator begin()
		{
			iterator it(_head->_next);
			return it;
		}

		iterator end()
		{
			iterator it(_head);
			return it;
		}

		//插入（在pos之前插入）
		iterator insert(iterator pos, const T& x)
		{
			//找到Pos位置的节点
			Node* cur = pos._node;
			//开一个新节点
			Node* newnode = new Node(x);
			//找pos的前一个节点
			Node* prev = cur->_prev;
			//连接  prev  newnode cur
			prev->_next = newnode;
			newnode->_prev = prev;
			newnode->_next = cur;
			cur->_prev = newnode;

			return iterator(newnode);
		}

		iterator erase(iterator pos)
		{
			//防止删掉哨兵位
			// pos end() 都是迭代器，_head是指针，所以不用
			assert(pos != end());


			//找到pos
			Node* cur = pos._node;
			//pos的前一个节点
			Node* prev = cur->_prev;
			//pos的后一个节点
			Node* next = cur->_next;

			//连接 prev    next
			prev->_next = next;
			next->_prev = prev;

			//删除节点
			delete cur;

			return iterator(next);
		}

		//尾删
		void pop_back()
		{
			erase(--end());
		}
		//头删
		void pop_front()
		{
			erase(begin());
		}
		//头插
		void push_front(const T& x)
		{
			insert(begin(), x);
		}

		////节点初始化
		////双链表有哨兵位
		//List()
		//{
		//	_head = new Node(T());//创建一个T（）类型的节点
		//	_head->_prev = _head;//节点前后都指向自己
		//	_head->_next = _head;
		//}

		//哨兵位头节点
		void empty_init()
		{
			_head = new Node(T());
			_head->_next = _head;
			_head->_prev = _head;
		}

		//节点初始化
		//双链表有哨兵位
		List()
		{
			//_head = new Node(T());//创建一个T（）类型的节点
			//_head->_prev = _head;//节点前后都指向自己
			//_head->_next = _head;

			empty_init();
		}

		//深拷贝
		//lt2(lt1)
		List(const List<T>& lt)
		{
			//先把原来list里面的数据初始化
			empty_init();
			//把lt1里面的数据一个一个尾插到lt2
			for (const auto& e : lt)
			{
				push_back(e);
			}
		}

		~List()
		{
			clear();
			delete _head;
			_head = nullptr;
		}

		void clear()
		{
			auto it = begin();
			while (it != end())
			{
				it = erase(it);
			}
		}

		//传值传参
		//lt1=lt3
		// 交换两个list的数据后，这两个list还在，所以用传引用返回
		List<T>& operator=(List<T> lt)//lt3出了当前作用域不销毁，所以用传引用返回
		{
			swap(_head, lt._head);//直接用库里面的函数
			return *this;
		}

		List(initializer_list<T> il)
		{
			empty_init();
			for (const auto& e : il)
			{
				push_back(e);
			}
		}

	private:
		Node* _head;
	};
}